The present invention relates to a method and apparatus for handling stored data and particularly, but not exclusively, to memory compaction during garbage collection in a real or virtual memory space of a data processing apparatus.
Garbage collection is the automated reclamation of system memory space after its last use by a programme. A number of examples of garbage collecting techniques are discussed in "Garbage Collection: Algorithms for Automatic Dynamic Memory Management" by R. Jones et al, pub. John Wiley & Sons 1996, ISBN 0-471-941484, at pages 1 to 18, and "Uniprocessor Garbage Collection Techniques" by P.R. Wilson, Proceedings of the 1992 International Wyrkshop on Memory Management, St. Malo, France, September 1992. While the storage requirements of many computer programs are simple and predictable, with memory allocation and recovery being handled by the programmer or a compiler, there is a trend toward languages having more complex patterns of execution such that the lifetimes of particular data structures can no longer be determined prior to run-time and hence automated reclamation of this storage, as the program runs, is essential.
One particular class of garbage collection/memory reclamation techniques, as described in the above-mentioned Wilson reference, is mark-compact collection. In common with many garbage collection techniques, it is a two-stage procedure and, as its name suggests, it involves first marking all stored objects that are still reachable by tracing a path or paths through the pointers linking data objects. Thereafter, the memory is compacted, moving the marked objects stored in the memory to a contiguous area of memory to leave a space containing only redundant objects, which space may then be reclaimed.
Fragmentaton of system memory is a problem which is particularly acute with garbage collected memory systems. Methods for compaction of memory, such as mark-compact collection, where all memory blocks are moveable are well known. However, the situation where there is a variety of fixed and moveable data, interleaved in an arbitrary fashion, causes problems.
Applying conventional defragmentation techniques in circumstances where there are unmoveable blocks may still leave memory in a partially fragmented state, that is to say composed of collected groups of filled memory blocks interspersed with more than one area of free memory. The consequence of this is that the allocator (the system function allotting storage locations to memory blocks) needs to be designed to work with partially fragmented memory. Also, an overall monitoring and control function must be applied to ensure that defragmentation actually results in a more useful memory organization than before compaction. As memory allocation patterns are arbitrary and unpredictable, the suitability of memory organizations for a particular size of allocation cannot be known before the allocation actually occurs.